<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2619：[Usaco 2012 Mar]Large Banner</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco 2012 Mar]Large Banner</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco 2012 Mar]Large Banner</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco 2012 Mar]Large Banner                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium"><span class="Apple-style-span" style="word-spacing: 0px; font: medium Arial,Microsoft Yahei,Simsun,sans-serif; text-transform: none; color: rgb(0,0,0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; orphans: 2; widows: 2; webkit-border-horizontal-spacing: 0px; webkit-border-vertical-spacing: 0px; webkit-text-decorations-in-effect: none; webkit-text-size-adjust: auto; webkit-text-stroke-width: 0px"><span class="Apple-style-span" style="color: rgb(70,70,70); line-height: 21px; font-family: simsun; text-align: left"><span class="Apple-style-span" style="word-spacing: 0px; font: medium Arial,Microsoft Yahei,Simsun,sans-serif; text-transform: none; color: rgb(0,0,0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; orphans: 2; widows: 2; webkit-border-horizontal-spacing: 0px; webkit-border-vertical-spacing: 0px; webkit-text-decorations-in-effect: none; webkit-text-size-adjust: auto; webkit-text-stroke-width: 0px"><span class="Apple-style-span" style="font-family: monospace">Large Banner [Nathan Pinsker, 2010] Bessie is returning from a long trip abroad to the Isle of Guernsey, and Farmer John wants to mount a nice &quot;Welcome Home&quot; banner for her arrival. Farmer John's field has integer dimensions M x N (1 &lt;= M, N &lt;= 100,000), and he has installed a post at every possible point in the field with integer coordinates (if we assign a coordinate system to the field so that (0,0) is in the lower-left corner and (M,N) is in the upper-right corner). Of these (M+1) * (N+1) points, Farmer John must pick two as the endpoints of the banner. Farmer John, being the perfectionist that he is, insists that the banner must be completely straight. This means that, for the two posts he chooses, there cannot be any other post on the line segment that the banner will form between them. Additionally, Farmer John wants the banner to have length at least L and at most H (1 &lt;= L &lt;= H &lt;= 150,000). Farmer John needs your help to figure out how many possible ways he can hang the banner. The banner is reversible, so switching the two endpoints of the banner counts as the same way to hang the banner. As this number may be very large, Farmer John simply wants to know what it is modulo B (1 &lt;= B &lt;= 1,000,000,000). Consider the example below, with M = 2 and N = 2: * * * * * * * * * Farmer John wants the length of the banner to be between 1 and 3 inclusive. Any choice of posts satisfies this length requirement, but note that eight pairs cannot be picked: (0, 0) and (2, 0): (1, 0) is on the line segment between them (0, 1) and (2, 1): (1, 1) is on the line segment between them (0, 2) and (2, 2): (1, 2) is on the line segment between them (0, 0) and (2, 2): (1, 1) is on the line segment between them (0, 0) and (0, 2): (0, 1) is on the line segment between them (1, 0) and (1, 2): (1, 1) is on the line segment between them (2, 0) and (2, 2): (2, 1) is on the line segment between them (0, 2) and (2, 0): (1, 1) is on the line segment between them Therefore, there are a total of (9 choose 2) - 8 = 28 possible locations. </span></span></span></span></span></p>
<p><span style="font-size: medium"><span class="Apple-style-span" style="word-spacing: 0px; font: medium Arial,Microsoft Yahei,Simsun,sans-serif; text-transform: none; color: rgb(0,0,0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; orphans: 2; widows: 2; webkit-border-horizontal-spacing: 0px; webkit-border-vertical-spacing: 0px; webkit-text-decorations-in-effect: none; webkit-text-size-adjust: auto; webkit-text-stroke-width: 0px"><span class="Apple-style-span" style="color: rgb(70,70,70); line-height: 21px; font-family: simsun; text-align: left">给出n,m,l,h，问有多少点A(ax,ay),B(bx,by)满足：ax,bx&isin;[0,n], ay,by&isin;[0,m]，l&lt;=AB&lt;=h，且线段AB上除A,B外无整点。</span></span></span></p></p><hr/><h3>输入格式</h3><p><p><span style="font-size: medium"><span class="Apple-style-span" style="word-spacing: 0px; font: medium Arial,Microsoft Yahei,Simsun,sans-serif; text-transform: none; color: rgb(0,0,0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; orphans: 2; widows: 2; webkit-border-horizontal-spacing: 0px; webkit-border-vertical-spacing: 0px; webkit-text-decorations-in-effect: none; webkit-text-size-adjust: auto; webkit-text-stroke-width: 0px"><span class="Apple-style-span" style="color: rgb(70,70,70); line-height: 21px; font-family: simsun; text-align: left"><span class="Apple-style-span" style="word-spacing: 0px; font: medium Arial,Microsoft Yahei,Simsun,sans-serif; text-transform: none; color: rgb(0,0,0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; orphans: 2; widows: 2; webkit-border-horizontal-spacing: 0px; webkit-border-vertical-spacing: 0px; webkit-text-decorations-in-effect: none; webkit-text-size-adjust: auto; webkit-text-stroke-width: 0px"><span class="Apple-style-span" style="font-family: monospace">&nbsp;INPUT FORMAT: * Line 1: Five space-separated integers: M, N, L, H and B.&nbsp;</span></span></span></span></span></p></p><hr/><h3>输出格式</h3><p><p>Line 1: One integer denoting the number of possible banners (modulo B).</p></p><hr/><h3>样例输入</h3><pre> 2 2 1 3 100
 </pre><hr/><h3>样例输出</h3><pre> 28</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2619" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2619" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>